Generating Functions

释义 Definition

生成函数：在组合数学与离散数学中，把一个数列的各项作为幂级数的系数，构造成一个形式幂级数（或解析函数），用来编码数列信息，并通过代数运算、微分/积分、函数变换等手段推导恒等式、递推关系与计数结果。常见类型包括普通生成函数（OGF）与指数生成函数（EGF）等。（在更广义语境下也可指概率、物理中的“生成泛函/生成函数”，但最常见的是组合数学用法。）

发音 Pronunciation (IPA)

/ˈdʒɛnəreɪtɪŋ ˈfʌŋkʃənz/

词源 Etymology

“generate”来自拉丁语 generare（“产生、生成”），与“genus”（“种类、类别”）同源；“function”来自拉丁语 functio（“执行、作用”）。合起来的“generating function(s)”字面义是“用来生成（信息/系数）的函数”，在19世纪以来的数学传统中逐渐固定为表示“用函数打包数列并用于推导”的工具术语。

例句 Examples

A generating function can turn a counting problem into an algebra problem.
生成函数可以把一个计数问题转化为一个代数问题。

Using generating functions, we derived a closed-form formula for the recurrence and proved the identity.
借助生成函数，我们为递推关系推出了封闭形式的公式，并证明了该恒等式。

相关词 Related Words

• Coefficient
• Power Series
• Recurrence
• Combinatorics
• Partition
• Convolution
• Ordinary Generating Function
• Exponential Generating Function

文学与名著中的用例 Literary Works

• Generatingfunctionology（Herbert S. Wilf）：以生成函数为核心的经典入门与工具书。
• An Introduction to the Theory of Numbers（G. H. Hardy & E. M. Wright）：在整数与分拆等章节中使用生成函数方法。
• Analytic Combinatorics（Philippe Flajolet & Robert Sedgewick）：系统发展生成函数与解析方法的权威著作。
• Concrete Mathematics（Graham, Knuth & Patashnik）：在求和、递推与计数技巧中频繁使用生成函数。